<!DOCTYPE html>
<html lang="zh-cmn-Hans" prefix="og: http://ogp.me/ns#" class="han-init">
<head>
  <meta charset="utf-8">
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <link rel="icon" href="http://upeng.github.io/favicon.ico">
  <title>upeng</title>
  <link rel="stylesheet" href="/css/style.css">
  <link rel="stylesheet" href="/lib/fancybox/jquery.fancybox-1.3.4.css">
  <!--在这里倒入jquery 方便处理部分页面的jquery-->
  <script src="https://cdn.staticfile.org/jquery/1.7/jquery.min.js" type="text/javascript" ></script>
</head>

<body>
	<header class="site-header navfixed-false">
  <div class="container">
      <h1><a href="/" title="upeng"><span class="octicon octicon-mark-github"></span> upeng</a></h1>
      <nav class="site-header-nav" role="navigation">
        
              
              <a href="/"  class=" site-header-nav-item hvr-underline-from-center" title="Home">Home</a>
        
              
              <a href="/categories/"  class=" site-header-nav-item hvr-underline-from-center" title="Categories">Categories</a>
        
              
              <a href="/bookmark/"  class=" site-header-nav-item hvr-underline-from-center" title="Bookmark">Bookmark</a>
        
              
              <a href="http://shareup.sinaapp.com"  class=" site-header-nav-item hvr-underline-from-center" title="Share">Share</a>
        
              
              <a href="/about/"  class=" site-header-nav-item hvr-underline-from-center" title="About">About</a>
        
      </nav>
  </div>
</header>

	
<section class="collection-head geopattern" data-pattern-id="判断一个整数的二进制中1的个数" >
    <div class="container">
        <div class="collection-title">
            <h1 class="collection-header">
                判断一个整数的二进制中1的个数
            </h1>
            
                <div class="collection-info">
                    <span class="meta-info">
                        <span class="octicon octicon-calendar"></span>
                        <time datetime="2016-12-13T15:54:24.000Z" itemprop="datePublished">2016-12-13</time>
                    </span>
                    
                        <span class="meta-info">
                            <span class="octicon octicon-file-directory"></span>
                            <a href='/categories/算法/' title=''>算法</a>
                        </span>
                    
                </div>
            
        </div>
    </div>
</section>
	<section class="container">
    <div class="columns">
        <!-- -->
        <div class="column three-fourths">
            <article class="article-content markdown-body">
                <p>无意间看到这个题目，最先想到是将整数转换成二进制，然后再统计这个二进制中有多少个1。对于php而言，这很容易实现，转成二进制可用<code>decbin()</code>这个函数，然后将二进制数按1位进行分割用str_split()，最后对分割后的数值进行foreach即可完成数据的统计，实际上这是最low的解决方案，网上大多数使用下面的算法进行求解，觉得很巧妙，于是就mark了！<br><a id="more"></a></p>
<h3 id="算法说明"><a href="#算法说明" class="headerlink" title="算法说明"></a>算法说明</h3><p>设x的二进制位表示为<br>x=a<sub>(n-1)</sub> a<sub>(n-2)</sub>…a<sub>0</sub></p>
<p>按从低位到高位的顺序，不失一般性，假设x的第i位为第一个为1的二进制位，即：a<sub>i</sub> = 1<br>此时有：<br> x  =  a<sub>(n-1)</sub> a<sub>(n-2)</sub> … a<sub>(i+1)</sub> 1 0 0 … 0       （式1)<br>x-1= a<sub>(n-1)</sub>a<sub>(n-2)</sub> …a<sub>(i+1)</sub> 0 1 1  … 1  （式2)<br>很明显，从式1和式2可以得出，在第一次 <code>x &amp; (x-1)</code> 后：<br>x  =  a<sub>(n-1)</sub> a<sub>(n-2)</sub> … a<sub>(i+1)</sub> 0 0 0 … 0</p>
<p>之后重复同样操作，直到x的二进制位中没有1为止，从上面可以看出，每执行过一次 <code>x &amp; (x-1)</code> 后，都会将x的<strong>二进制位中为1的最低位的值变为0，并记数加1</strong>。目前而言，一个整数最大64bit，所有三种方法执行起来都可以认为是O(1)。</p>
<h3 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h3><pre><code>&lt;?php
$number = $argv[1];
$counter = 0;
while ($number)
{
    $counter += 1;
    $number = $number &amp; ($number-1);

}

echo $counter . PHP_EOL;
</code></pre>
            </article>
            
                <div class="share">
                    <!--开启分享-->
<div class="share-component" data-disabled="google,twitter,facebook" data-description="无意间看到这个题目，最先想到是将整数转换成二进制，然后..."></div>

<script src="/js/share.min.js"></script>

                </div>    
            
            
                
<div class="comments">
	<div class="ds-thread" data-thread-key="algorithm" data-title="判断一个整数的二进制中1的个数" data-url="http://upeng.github.io/2016/12/13/algorithm/"></div>
	<script type="text/javascript">
	var duoshuoQuery = {short_name:"upeng"};
		(function() {
			var ds = document.createElement('script');
			ds.type = 'text/javascript';ds.async = true;
			ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
			ds.charset = 'UTF-8';
			(document.getElementsByTagName('head')[0]
			 || document.getElementsByTagName('body')[0]).appendChild(ds);
		})();
	</script>
</div>

            
        </div>
        <div class="column one-fourth">
            
                
                


<h3>Post Directory</h3>

<div id="post-directory-module">
	<section class="post-directory">
		<p><strong class="toc-title">文章目录</strong></p>
		<ol class="toc"><li class="toc-item toc-level-3"><a class="toc-link" href="#算法说明"><span class="toc-text">算法说明</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#代码实现"><span class="toc-text">代码实现</span></a></li></ol>
	</section>
</div>
            
        </div>
    </div>
</section>

<footer class="container">
    <div class="site-footer" role="contentinfo">
        <div class="copyright left mobile-block">
                © 2016
                <span title="yupeng">yupeng</span>
                <a href="javascript:window.scrollTo(0,0)" class="right mobile-visible">TOP</a>
        </div>

        <ul class="site-footer-links right mobile-hidden">
            <li>
                <a href="javascript:window.scrollTo(0,0)" >TOP</a>
            </li>
        </ul>

        <a href="https://github.com/upeng" target="_blank" aria-label="view source code">
            <span class="mega-octicon octicon-mark-github" title="GitHub"></span>
        </a>

        <ul class="site-footer-links mobile-hidden">
            
                  
                  <li>
                    <a href="/"  title="Home">Home</a>
                  </li>
            
                  
                  <li>
                    <a href="/categories/"  title="Categories">Categories</a>
                  </li>
            
                  
                  <li>
                    <a href="/bookmark/"  title="Bookmark">Bookmark</a>
                  </li>
            
                  
                  <li>
                    <a href="http://shareup.sinaapp.com"  title="Share">Share</a>
                  </li>
            
                  
                  <li>
                    <a href="/about/"  title="About">About</a>
                  </li>
            
            <li>
                <a href="/atom.xml">
                    <span class="octicon octicon-rss" style="color:orange;"></span>
                </a>
            </li>
        </ul>
    </div>
</footer>


		<script src="/js/geopattern.js"></script>

		
			<script src="/js/toc.js"></script>
		

		<script src="/js/highlight.pack.js"></script>
		<script src="/lib/fancybox/jquery.fancybox-1.3.4.pack.js"></script>

		<script src="/js/index.js"></script>

		 <script src="/js/popular_repo.js"></script> 

	</body>
</html>